95. 不同的二叉搜索树 II

Similar Question

leading to the advanced question

108. 将有序数组转换为二叉搜索树

823. 带因子的二叉树

Solution Tips

方案一: 记忆化搜索 + 递归

比如说输入 n = 3，算法返回 5，因为共有如下 5 种不同的 BST 结构存储 {1,2,3}：

首先，这棵 BST 的根节点总共有几种情况？

显然有 5 种情况对吧，因为每个数字都可以作为根节点。

比如说我们固定 3 作为根节点，这个前提下能有几种不同的 BST 呢？

根据 BST 的特性，根节点的左子树都比根节点的值小，右子树的值都比根节点的值大。

所以如果固定 3 作为根节点，左子树节点就是 {1,2} 的组合，右子树就是 {4,5} 的组合。

左子树的组合数和右子树的组合数乘积就是 3 作为根节点时的 BST 个数。

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
  // 备忘录的值初始化为 0，因为是从1开始的  所以二维数组的初始长度为n+1
  let memo = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(0));
  let count = (lo, hi) => {
    // base case，显然当lo > hi闭区间[lo, hi]肯定是个空区间，也就对应着空节点 null，
    // 虽然是空节点，但是也是一种情况，所以要返回 1 而不能返回 0
    if (lo > hi) return 1;
    // 必须是base case在备忘录前面判断  不然就越界了
    if (memo[lo][hi] != 0) return memo[lo][hi];
    let res = 0;
    for (let i = lo; i <= hi; i++) {
      // i 的值作为根节点 root
      let left = count(lo, i - 1);
      let right = count(i + 1, hi);
      // 左右子树的组合数乘积是 BST 的总数
      res += left * right;
    }
    memo[lo][hi] = res;
    return res;
  };
  // 计算闭区间 [1, n] 组成的 BST 个数
  return count(1, n);
};

var generateTrees = function (n) {
  if (n == 0) return [];
  // 备忘录，避免重复计算
  let memo = new Map();
  /* 构造闭区间 [lo, hi] 组成的 BST */
  const build = (lo, hi) => {
    let res = [];
    // base case，显然当lo > hi闭区间[lo, hi]肯定是个空区间，也就对应着空节点 null，
    if (lo > hi) {
      res.push(null);
      return res;
    }
    let memoKey = `${lo}&${hi}`;
    // 如果缓存当中有就直接拿
    if (memo.has(memoKey)) return memo.get(memoKey);
    // 1、穷举 root 节点的所有可能。
    for (let i = lo; i <= hi; i++) {
      // 2、递归构造出左右子树的所有合法 BST。
      let leftTree = build(lo, i - 1);
      let rightTree = build(i + 1, hi);
      // 3、给 root 节点穷举所有左右子树的组合。
      for (let left of leftTree) {
        for (let right of rightTree) {
          res.push(new TreeNode(i, left, right));
        }
      }
    }
    // 将结果集放入到缓存中
    memo.set(memoKey, res);
    return res;
  };
  // 构造闭区间 [1, n] 组成的 BST
  return build(1, n);
};

方法二: 动态规划

var numTrees = function(n) {
    const G = new Array(n + 1).fill(0);
    G[0] = 1;
    G[1] = 1;

    for (let i = 2; i <= n; ++i) {
        for (let j = 1; j <= i; ++j) {
            G[i] += G[j - 1] * G[i - j];
        }
    }
    return G[n];
};